package hot100;


/*
 * Author：江松
 * Date：2023/4/6 15:21
 *
 二叉树的最近公共祖先：
 使用后序遍历，遍历左子树右子树，然后进行比对
  如果left 和 right都不为空，说明pq分别在root两侧，当前root就是最近公共节点
  如果left为空，right不为空，说明都在右侧right，返回right，反之亦然。
 */

public class Main236 {
      public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          if(root==null||root==p||root==q){
              return root;
          }
          TreeNode left=lowestCommonAncestor(root.left,p,q);
          TreeNode right=lowestCommonAncestor(root.right,p,q);
          //说明寻找左右子树时，没找到底就发现了pq，因此p，q位于两侧
          if(left!=null&&right!=null)return root;
          //左边没找到，说明都在右边
          else if(left==null)return right;
          else return left;
    }
}
